#include "Tree.h"

int FGetSize(Node* root){
    int allCs = 0;
    for(int i = 0; i < root->cSize; i++){
        allCs += FGetSize(root->children[i]);
    }
    return root->cSize + allCs;
}
int GetSize(Node* root){
    return FGetSize(root) + 1;
}
Node* GetFirstChild(Node* root){
    assert(root != NULL);

    if(root->cSize >0)
        return root->children[0];
}
Node* GetNextSibling(Node* root){
    assert(root != NULL);

    if(root->parent){
        Node* parent = root->parent;
        for(int i = 0; i < parent->cSize;i++) {
            if(parent->children[i] == root && i + 1 < parent->cSize)
                return parent->children[i + 1];
        }
    }
}
int GetHeight(Node* root){
    assert(root != NULL);
    int height = 0;

    for(int i = 0; i< root->cSize; i++){
        int childHeight =1 + GetHeight(root->children[i]);
        if(childHeight > height)
            height = childHeight;
    }

    return height;
}
//创建节点
Node* Init(char* key){
    Node* root = (Node*) malloc(sizeof(Node));
    root->key = key;
    root->parent = NULL;

    Node** nodes = (Node**) malloc(sizeof(Node*) * CMAX);
    memset(nodes,0,sizeof(Node*) * CMAX);
    root->children = nodes;

    root->cMax = CMAX;
    root->cSize = 0;
    return root;
}
Node* AddNode(Node* parent, char* key){
    if(parent){
        Node* node = Init(key);
        if(parent->cSize >= parent->cMax){
            parent->cMax *= 2;
            Node** nodes = (Node**) malloc(sizeof(Node*) * parent->cMax);
            memset(nodes,0,sizeof(Node*) * parent->cMax);
            memcpy(nodes,parent->children,sizeof(Node*) * parent->cMax/2);
            free(parent->children);
            parent->children = nodes;
        }
        int index = parent->cSize ++;
        parent->children[index] = node;
        node->parent = parent;
        return node;
    } else {
        return Init(key);
    }
}
void DeleteAll(Node* parent){
    for(int i = 0; i < parent->cSize; i++){
        DeleteAll(parent->children[i]);
    }
    free(parent);

}
void DeleteChildren(Node* parent, int index){
    assert(parent != NULL && parent->cSize > index);
    Node** nodes = parent->children;
    DeleteAll(nodes[index]);

    if(index + 1 < parent->cSize){
        nodes[index] = nodes[parent->cSize - 1];
        nodes[parent->cSize - 1] = NULL;
    } else {
        nodes[index] = NULL;
    }
    parent->cSize--;

}
void FPreOrder(Node* root){
    printf("%s,",root->key);
    for(int i = 0; i < root->cSize;i++){
        FPreOrder(root->children[i]);
    }
}
void PreOrder(Node* root){
    FPreOrder(root);
    printf("\n");
}
void FPostOrder(Node*root){
    for(int i = 0; i < root->cSize;i++){
        FPreOrder(root->children[i]);
    }
    printf("%s,",root->key);
}
void PostOrder(Node * root){
    FPostOrder(root);
    printf("\n");
}
void FLevelOrder(Node* root){
    Node** nodes = root->children;
    for(int i = 0; i < root->cSize; i++){
        printf("%s,", nodes[i]->key);
    }

    for(int i = 0; i < root->cSize; i++){
        FLevelOrder(nodes[i]);
    }
}
void LevelOrder(Node* root){
    printf("%s,",root->key);
    FLevelOrder(root);
    printf("\n");
}